#include<iostream>
#include<algorithm>
namespace MyBBS{
  template<class K,class V>
    class TreeNode{
      public:
      TreeNode(const std::pair<K,V>& data)
        :_left(nullptr)
         ,_right(nullptr)
         ,_parent(nullptr)
         ,_factor(0)
      {
        _data.first = data.first;
        _data.second = data.second;
      }
        TreeNode* _left;
        TreeNode* _right;
        TreeNode* _parent;
        std::pair<K,V> _data;
        int _factor;
  };
  template<class K,class V>
  class BBSTree{
  public:
    BBSTree():_root(nullptr){}

    void print()
    {
      _print(_root);
    }
    bool IsBalance()
    {
      if(_root == nullptr || _IsBalance(_root))
      {
        return true;
      }
      else{
        return false;
      }
    }
    void insert(const std::pair<K,V>& node)
    {
      if(_root == nullptr)
      {
        _root = new TreeNode<K,V>(node);
      }
      //找插入点
      TreeNode<K,V>* now = _root;
      TreeNode<K,V>* now_parent = nullptr;
      while(now)
      {
        if(now->_data.first < node.first)
        {
          now_parent = now;
          now = now->_right;
        }
        else if(now->_data.first > node.first)
        {
          now_parent = now;
          now = now->_left;
        }
        else
        {
          return;
        }
      }
      TreeNode<K,V>* newnode = new TreeNode<K,V>(node);
      if(now_parent->_data.first < newnode->_data.first)
      {
        now_parent->_right = newnode;
        now_parent->_factor++;
      }
      else if(now_parent->_data.first > newnode->_data.first){
        now_parent->_left = newnode;
        now_parent->_factor--;
      }
      else{
        std::cerr << "insert is error" << std::endl;
        return;
      }
      newnode->_parent = now_parent;
      //调整平衡因子
      TreeNode<K,V>* nownode = now_parent;
      now_parent = now_parent->_parent;
      while(true)
      {
        if(now_parent == nullptr || now_parent->_factor == 0)
        {
          break;
        }
        if(now_parent->_left == nownode)
        {
          now_parent->_factor--;
        }
        else if(now_parent->_right == nownode)
        {
          now_parent->_factor++;
        }
        else{
          break;
        }
        if(now_parent->_factor == 2 || now_parent->_factor == -2)
        {
          //需要旋转
          Adjust(nownode);
          break;
        }
        nownode = now_parent;
        now_parent = now_parent->_parent;
      }
    }

  private:
    void Adjust(TreeNode<K,V>* node)
    {
      if(node->_factor == 2)
      {
        TreeNode<K,V>* Rnode = node->_right;
        if(Rnode->_factor == 1)
        {
          //左旋
          Levorotation(node);
        }
        else if(Rnode->_factor == -1)
        {
          //右左双旋
          RLRotation(node);
        }
      }
      else if(node->_factor == -2)
      {
        TreeNode<K,V>* Lnode = node->_left;
        if((Lnode->_factor == -1))
        {
          //右旋
          Dextrorotation(node);
        } 
        else if(Lnode->_factor == 1)
        {
          //左右双旋
          LRRotation(node);
        }
      }
    }
    //左旋
    void Levorotation(TreeNode<K,V>* node)
    {
      TreeNode<K,V>* Rnode = node->_right;
      TreeNode<K,V>* RLnode = Rnode->_left;
      //adjust _left _right
      Rnode->_left = node;
      node->_right = RLnode;
      //adjust _parent
      if(node->_parent)
      {
        if(node->_parent->_left == node)
        {
          node->_parent->_left = Rnode;
        }
        else{
          node->_parent->_right = Rnode;
        }
      }
      node->_parent = Rnode;
      Rnode->_parent = node->_parent;
      //注意可能RLnode该指针为空
      if(RLnode)
      {
        RLnode->_parent = node;
      }
      if(node == _root)
      {
        _root = Rnode;
      }
      //adjust _factor
      node->_factor = Rnode->_factor = 0;
    }
    //右旋
    void Dextrorotation(TreeNode<K,V>* node)
    {
      TreeNode<K,V>* Lnode = node->_left;
      TreeNode<K,V>* LRnode = Lnode->_right;
      //adjust _left _right
      Lnode->_left = node;
      node->_left = LRnode;
      //adjust _parent
      if(node->_parent)
      {
        if(node->_parent->_left == node)
        {
          node->_parent->_left = Lnode;
        }
        else{
          node->_parent->_right = Lnode;
        }
      }
      Lnode->_parent = node->_parent;
      node->_parent = Lnode;
      //注意可能LRnode该指针为空
      if(LRnode)
      {
        LRnode->_parent = node;
      }
      if(node == _root)
      {
        _root = Lnode;
      }
      //adjust _factor
      node->_factor = Lnode->_factor = 0; 

    }
    //右左双旋
    void RLRotation(TreeNode<K,V>* node)
    {
      TreeNode<K,V>* Rnode = node->_right;
      TreeNode<K,V>* RLnode = Rnode->_left;
      int factor = RLnode->_factor;
      Dextrorotation(Rnode);
      Levorotation(node);
      //adjust _factor
      if(factor == 1)
      {
        node->_factor = -1;
        Rnode->_factor = RLnode->_factor = 0;
      }
      else{
        Rnode->_factor = 1;
        node->_factor = RLnode->_factor = 0; 
      }

    }
    //左右双旋
    void LRRotation(TreeNode<K,V>* node)
    {
      TreeNode<K,V>* Lnode = node->_left;
      TreeNode<K,V>* LRnode = Lnode->_right;
      int factor = LRnode->_factor;
      Levorotation(Lnode);
      Dextrorotation(node);
      if(factor == 1)
      {
        Lnode->_factor = 1;
        LRnode->_factor = node->_factor = 0;
      }
      else{
        node->_factor = -1;
        LRnode->_factor = Lnode->_factor = 0;
      }
    }
    void _print(TreeNode<K,V>* root)
    {
      if(root== nullptr)
      {
        return;
      }
      _print(root->_left);
      std::cout << root->_data.first << "  "<< root->_data.second << std::endl;
      _print(root->_right);
    }
    bool _IsBalance(TreeNode<K,V>* root)
    {
      if(root == nullptr)
      {
        return true;
      }
      bool isbalance = false;
      int x = GetLH(root)-GetRH(root);
      if(x == 1 || x == -1 || x == 0)
      {
        isbalance = true;
      }
      else{
        std::cerr << "error" << root->_data.first << std::endl;  
      }
      return isbalance && _IsBalance(root->_left) && _IsBalance(root->_right); 
    }
    int GetRH(TreeNode<K,V>* root)
    {
      if(root == nullptr)
      {
        return 0;
      }
      return std::max(GetRH(root->_left),GetRH(root->_right))+1;
    }
    int GetLH(TreeNode<K,V>* root)
    {
      if(root == nullptr)
      {
        return 0;
      }
      return std::max(GetRH(root->_left),GetRH(root->_right))+1;
    }
  private:
    TreeNode<K,V>* _root;
  };
}
